The elementary set of patterns available in natural images is finite, and can typically consist of edges, wedges, curves, smooth regions and textures. These elementary patterns can be stacked together as columns of a “dictionary” matrix. Any local region commonly referred to as a “patch” in a natural image can be represented as a linear combination of a small number of columns from the dictionary. This operation is referred to as sparse coding, and computing sparse codes for images is a nonlinear and complex procedure. The dictionaries for sparse coding may be pre-defined but they can also be adapted to a set of training examples. Dictionary learning is an iterative procedure that is often times is computationally expensive and usually requires a large training set is necessary to obtain good dictionaries.
Sparse approximation using learned dictionaries have been shown to provide improved performance for restoring degraded data in applications such as image denoising, inpainting, deblurring, single image super resolution, and compressive sensing.